package main.leetcode.offer.firstround.from03to50;

/**
 * 42.连续子数组的最大和
 *
 * <p>输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * <p>要求时间复杂度为O(n)。
 *
 * <p>
 *
 * <p>示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 * <p>提示：1 <= arr.length <= 10^5，-100 <= arr[i] <= 100
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex42 {
    public static void main(String[] args) {
        System.out.println(new ex42().maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
    // 动态规划
    //    public int maxSubArray(int[] nums) {
    //        int n = nums.length;
    //        if (n < 2) return nums[0];
    //        int[] dp = new int[n];
    //        dp[0] = nums[0];
    //        int res = dp[0];
    //        for (int i = 1; i < n; i++) {
    //            if (dp[i - 1] < 0) dp[i] = nums[i];
    //            else dp[i] = dp[i - 1] + nums[i];
    //            res = Math.max(res, dp[i]);
    //        }
    //        return res;
    //    }

    // 贪心
    //    public int maxSubArray(int[] nums) {
    //        int n = nums.length;
    //        if (n < 2) return nums[0];
    //        int currSum = Integer.MIN_VALUE;
    //        int res = currSum;
    //        for (int i = 0; i < n; i++) {
    //            if (currSum < 0) currSum = nums[i];
    //            else currSum += nums[i];
    //            res = Math.max(res, currSum);
    //        }
    //        return res;
    //    }

    // 分治
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n < 2) return nums[0];
        return helper(nums, 0, n - 1);
    }

    private int helper(int[] nums, int lo, int hi) {
        if (lo >= hi) return nums[lo];
        int mid = lo + (hi - lo) / 2;
        int leftSum = helper(nums, lo, mid); // 左部连续子数组最大和
        int rightSum = helper(nums, mid + 1, hi); // 右部连续子数组最大和
        int crossSum = crossSum(nums, lo, hi, mid); // 横跨中点的连续子数组最大和
        return Math.max(Math.max(leftSum, rightSum), crossSum); // 返回三者中最大值
    }

    private int crossSum(int[] nums, int lo, int hi, int mid) {
        if (lo >= hi) return nums[lo];
        int i, currSum;

        // 从mid向左扫描，得到左部连续最大和
        int leftSum = Integer.MIN_VALUE;
        for (i = mid, currSum = 0; i >= lo; --i) {
            currSum += nums[i];
            leftSum = Math.max(leftSum, currSum);
        }

        // 从mid+1向右扫描，得到右部连续最大和
        int rightSum = Integer.MIN_VALUE;
        for (i = mid + 1, currSum = 0; i <= hi; ++i) {
            currSum += nums[i];
            rightSum = Math.max(rightSum, currSum);
        }

        // 返回左右部之和
        return leftSum + rightSum;
    }
}
